package com.bigshen.algorithm.hHeap.solution01TopK;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 215. Kth Largest Element in an Array
 * Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
 *
 * Example 1:
 *
 * Input: [3,2,1,5,6,4] and k = 2
 * Output: 5
 * Example 2:
 *
 * Input: [3,2,3,1,2,4,5,5,6] and k = 4
 * Output: 4
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {

    // 快排或者最大堆来实现
    public int findKthLargest(int[] nums, int k) {

        if (null == nums || nums.length == 0 || k < 1 || k > nums.length) {
            return -1;
        }

        int maxK = 0;

        // by maxHeap
        //maxK = byHeap(nums, k);

        // by quickSort
        //quickSort(nums, 0, nums.length-1);
        //maxK = nums[nums.length-k];
        maxK = quickSortSearch(nums, 0, nums.length-1, nums.length-k);

        return maxK;
    }

    //
    private int quickSortSearch(int[] nums, int start, int end, int k) {
        if (start >= end) {
            return nums[start];
        }
        int left = start;
        int right = end;
        int tmp = nums[start];
        while (left < right) {
            // 右侧找比tmp小的值
            while (left < right && nums[right] >= tmp) {
                right--;
            }
            // 移至左侧
            if (left < right && nums[right] < tmp) {
                nums[left] = nums[right];
                left++;
            }
            // 左侧找比tmp大的值
            while (left < right && nums[left] <= tmp) {
                left++;
            }
            // 移至右侧
            if (left < right && nums[left] > tmp) {
                nums[right] = nums[left];
                right--;
            }
        }
        nums[left] = tmp;
        if (k == left) {
            return tmp;
        } else if (k < left){
            return quickSortSearch(nums, start, left-1, k);
        } else {
            return quickSortSearch(nums, left+1, end, k);
        }

    }

    // 快速排序 O(nlogn)
    private void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int left = start;
        int right = end;
        int tmp = nums[start];
        while (left < right) {
            // 右侧找比tmp小的值
            while (left < right && nums[right] >= tmp) {
                right--;
            }
            // 移至左侧
            if (left < right && nums[right] < tmp) {
                nums[left] = nums[right];
                left++;
            }
            // 左侧找比tmp大的值
            while (left < right && nums[left] <= tmp) {
                left++;
            }
            // 移至右侧
            if (left < right && nums[left] > tmp) {
                nums[right] = nums[left];
                right--;
            }
        }
        nums[left] = tmp;
        quickSort(nums, start, left-1);
        quickSort(nums, left+1, end);
    }

    // 最大堆：依赖堆属性'最大堆'，最大值在第一位，找第k大的值，只需将前k-1位弹出，到第k位返回
    private int byHeap(int[] nums, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });
        for (int i = 0; i < nums.length; i ++) {
            maxHeap.offer(nums[i]);
        }
        for (int i = 0; i < k-1; i ++) {
            maxHeap.poll();
        }
        return maxHeap.poll();
    }

}
